<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 12, Exercise 27<BR>

<BR>

</H1>

The solution is similar to that for Exercise 27.<br><br>



To input a weighted digraph we first destroy the old digraph stored in the 

object <code class=code>*this</code>.

Next, we input the number of vertices and edges in the new digraph;

verify that these numbers are legitimate (i.e., neither is less

than zero and the number of edges does not exceed the number of

edges in a complete digraph with the given number of vertices);

input the value <code class=code>NoEdge</code> to use

to represent an edge that is not in the digraph;

allocate a 2D array

<code class=code>a[][]</code> of the needed size; and finally read in the

edges one by one.  Each edge can be added to the data structure

being constructed using the function

<code class=code>Add</code>.

Recall that

<code class=code>Add</code> throws an exception when an attempt is

made to add an edge that is already in the digraph.  Therefore,

we need to not check for duplicate edges in the code we are to write.

<br><br>

We define two public member functions <code class=code>Input</code>

as shown below.



<HR class = coderule>

<pre class = code>

void Input() {Input(cin);}



template &lt;class T&gt;

void AdjacencyWDigraph&lt;T&gt;::Input(istream&amp; in)

{// Input the cost adjacency matrix.

   // first delete the old digraph

   Delete2DArray(a,n+1);



   // input number of vertices and edges

   cout &lt;&lt; "Enter the number of vertices in the digraph"

        &lt;&lt; endl;

   cin &gt;&gt; n;

   if (n &lt; 0) throw BadInput();

   cout &lt;&lt; "Enter the number of edges in the digraph" &lt;&lt; endl;

   int E;

   cin &gt;&gt; E;

   if (E &lt; 0 || E &gt; n*(n-1)) throw BadInput();

   cout &lt;&lt; "Enter value to use for no edge" &lt;&lt; endl;

   cin &gt;&gt; NoEdge;



   // create a new 2D array a[][] and initialize to NoEdge

   Make2DArray(a, n+1, n+1);

   // initalize to digraph with no edges

   for (int i = 1; i &lt;= n; i++)

      for (int j = 1; j &lt;= n; j++)

         a[i][j] = NoEdge;

   e = 0;



   // now input the edges and add them to the

   // a[][]

   int u, v;  // edge end points

   T w;       // edge weight

   for (int i = 1; i &lt;= E; i++) {

      cout &lt;&lt; "Enter edge " &lt;&lt; i &lt;&lt; endl;

      in &gt;&gt; u &gt;&gt; v &gt;&gt; w;

      Add(u,v,w);

      }

}

<hr class=coderule>

</pre>

<br><br>



The operator

<code class=code>&gt;&gt;</code> may be overloaded using the code given below.



<HR class = coderule>

<pre class = code>

// overload &gt;&gt;

template &lt;class T&gt;

istream&amp; operator&gt;&gt;(istream&amp; in, AdjacencyWDigraph&lt;T&gt;&amp; x)

   {x.Input(in); return in;}

<HR class = coderule>

</pre>

<br><br>



The code to output a digraph is already included in the file

<code class=code>awdgraph.h</code>.  To make it easy to

overload the operator <code class=code>&lt;&lt;</code>, we modify

it as below.



<HR class = coderule>

<pre class = code>

void Output() const

   {Output(cout);}



template &lt;class T&gt;

void AdjacencyWDigraph&lt;T&gt;::Output(ostream&amp; out) const

{// Output the adjacency matrix.

   for (int i = 1; i &lt;= n; i++) {

      for (int j = 1; j &lt;= n; j++)

         out &lt;&lt; a[i][j] &lt;&lt; " ";

      out &lt;&lt; endl;}

}

<hr class=coderule>

</pre>

<br><br>



The operator <code class=code>&gt;&gt;</code> may now be overloaded

as below.



<HR class = coderule>

<pre class = code>

// overload &lt;&lt;

template &lt;class T&gt;

ostream&amp; operator&lt;&lt;(ostream&amp; out, const AdjacencyWDigraph&lt;T&gt;&amp; x)

   {x.Output(out); return out;}

<hr class=coderule>

</pre>

<br><br>

The above codes, a test file, test data, and output can be found in the files

<code class=code>awdgph2.*</code>.





</FONT>

</BODY>

</HTML>

